/*
 * @lc app=leetcode id=198 lang=cpp
 *
 * [198] House Robber
 */
class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len < 1) {
            return 0;
        }
        
        vector<int> memo(len+1, 0);
        memo[0] = 0;
        memo[1] = nums[0];

        for (int i=2; i<=len; i++) {
            if (memo[i-2] + nums[i-1] > memo[i-1]) {
                memo[i] = memo[i-2] + nums[i-1];
            } else {
                memo[i] = memo[i-1];
            }
        }

        return memo[len];
    }
};

